package model;

@SuppressWarnings("unchecked")
public class ShellSort extends Sorter {

    public ShellSort() {
	super();
	statistics = new Statistics();
    }

    @Override
    public void sort(Comparable[] workArray) {
	long beforeTime = System.nanoTime();

	for (int gap = workArray.length / 2; gap > 0; gap = gap == 2 ? 1
		: (int) (gap / 2.2)) {
	    for (int i = gap; i < workArray.length; i++) {
		Comparable tmp = workArray[i];
		int j = i;

		for (; j >= gap && tmp.compareTo(workArray[j - gap]) < 0;statistics.incrementChecks(), j -= gap) {
		    workArray[j] = workArray[j - gap];
		    // Swap
		    // -----------------
		    statistics.incrementSwaps();
		    if (simulation)
			PushSwapToQueue(j, j - gap);
		    // -----------------
		}
		workArray[j] = tmp;
	    }
	}

	long afterTime = System.nanoTime();
	statistics.setRunTime(afterTime - beforeTime);
    }

    @Override
    public int getComplexity(int arraySize) {
	return (int) Math.pow(arraySize, 2);
    }

    public static void main(String[] args) {
	Comparable[] a = new Integer[] { -7, -1555, 5, 7, 8, 1, 0, -4, 91, 6,
		15, 30 };
	ShellSort sorter = new ShellSort();
	sorter.sort(a);
	for (int i = 0; i < a.length; i++)
	    System.out.println(a[i]);
    }
}
